\documentclass{article}

\begin{document}

\section{Implementation details}

\subsection{Join}

We implemented join simply by repeatedly yielding control until the target thread's status has been changed to {\tt statusFinished}.

\subsection{Condition Variables}

The condition variables were implemented in the Condition2.java class. 
They use the interrupt disabling methods directly from the machine for atomic instructions. 
A waitQueue is also part of the implementation and it keeps tracks of the waiting threads. 
The waitQueue comes from the current Scheduler class so priority is determined in the same manner as the threads when scheduled. 
\textit{sleep} puts the current thread in the waiting queue and then to sleep. 
\textit{wake} wakes the top thread in the waiting queue (depending on priority). 
\textit{wakeAll} wakes up all threads in the waiting queue. 

\subsection{Alarm}

The Alarm.java file was modified to use a HashMap to store all the waiting threads and there corresponding wait times. 
When the timer interrupts, it checks all of the threads and if the time has past, interrupts wakes up the thread. 
The interrupt processing checks each thread in the loop. 
This could be improved but it was considered a lot of processing and could have possibly included many other classes and an attempt was made to keep this simple. 
After waking up any waiting threads, the interrupt yields the current thread.

\subsection{Communicator}

The communicator class has one lock, two condition variables  ({\tt speakers} and {\tt listeners}), and counters of the number of threads waiting to speak and listen. 

When a thread wants to speak, it first acquires the lock and increments the {\tt numSpeakers} counter. If there are already threads waiting to speak, or if there are no threads ready to listen, it sleeps on the {\tt speaking} condition. It will be woken up by a listener later. Once it wakes up from the that sleep (or if it just passes through because there is a listener ready), it sets the {\tt currentWord} property to its word, and wakes up a listener, which will then pick up the word. After it wakes up the listener, it just releases the lock and returns.

When a thread wants to listen, it first acquires the lock and increments the {\tt numListeners} counter. If there are speakers waiting to speak and this is the first listener, it wakes up a speaker. Then it goes to sleep on the listening condition, to be woken later by a speaker after it has spoken. When it is woken, it takes the word currently in the {\tt currentWord} property, and decrements the {\tt numSpeakers} and {\tt numListeners} properties to indicate that the word has been exchanged and this speaker and listener are done. Then if there are more speakers and listeners, it wakes up a speaker, which will in turn wake up the next listener. Then it releases the lock and returns.

\subsection{Priority Scheduling}

We implemented priority scheduling by using a priority queue based on the heap data structure described in Cormen, Leiserson, Rivest, and Stein. We would have used {\tt java.lang.PriorityQueue}, except that class does not directly support {\em increase-key} or {\em decrease-key} operations, which are required in order to change the priority of a thread that is already in a queue.

\subsubsection{PriorityQueue Properties}

The PriorityQueue class keeps the following properties:

\begin{description}
\item[threads] The heap of threads currently waiting on the queue.
\item[owner] A pointer to the thread that currently ``owns'' the queue, or null if noone owns the queue.
\item[time] A ticker that is incremented each time a thread is added to the queue, so that we can compare threads by their time of entry.
\end{description}

\subsubsection{ThreadState Properties}

Each {\tt ThreadState} keeps the following properties:

\begin{description}
\item[waitQueue] The queue that the thread is currently waiting on, or null if it's not on a queue.
\item[entryTime] The time that the thread entered {\tt waitQueue}, or undefined if it's not in a queue.

\item[index] The thread's index in its wait queue, or undefined if it's not in a queue.
\item[ownedQueues] A set of PriorityQueues that are currently owned by this thread.
\item[thread] A pointer to the thread associated with this ThreadState.
\item[priority] The thread's current priority.
\item[effectivePriority] The thread's cached effective priority (see below for a detailed description of this calculation).
\end{description}

The {\tt ThreadState}s are ordered in the heap according to their effective priority, and then by their entry time. The {\tt compareTo} method compares two thread states and indicates which one should be released first.

Note that a {\tt ThreadState} knows its index in the {\tt PriorityQueue} at all times. This allows us to change the effective priority of a thread state while it is in a queue, and then move it to the proper position in the queue in $O(lg(n))$ time, without having to search through the queue for it.

\subsubsection{Calculating Effective Priority}

Let $T$ be the set of active threads. Let $Q$ be the set of all thread queues that have been produced by {\tt PriorityScheduler.newThreadQueue()}. Let $p_i$ be the priority of thread $i$, and $p_{ei}$ be the effective priority for thread $i$. Let $owner(q, t)$ indicate that thread $t$ is the current owner of queue $q$. Let $waiting(q, t)$ indicate that thread $t$ is currently waiting on queue $q$. Let $transferpriority(q)$ indicate that queue $q$ transfers priority.

Observe that the effective prioity $p_{ei}$ of a thread $t_i$ is the largest effective priority of any thread $t_j$ that is waiting on a queue $q$ that transfers priority and is owned by $t_i$.

\[p_{ei} = max(p_{ej} | waiting(q, t_j) \wedge q \in (q | owner(q, t_i) \wedge transferpriority(q))\]

A thread's effective priority can change because of the following events:

\begin{itemize}
\item When a new thread $t_k$ is added to a queue $q$ owned by $t_i$, and $p_{ek} > p_{ei}$, we need to increase the effective priority $p_{ei}$ of thread $i$ to be equal to $p_{ek}$.
\item Likewise, suppose we increase the priority of a thread $t_k$ that is waiting on a queue owned by $t_i$, such that $p_{ek} > p_{ei}$. We need to set $p_{ei} = p_{ek}$.
\item Now suppose we decrease the priority of a thread $t_k$ that is waiting on a queue $q$ owned by $t_i$. If $t_k$ had previously been the highest-priority thread waiting on $q$, then $t_k$ might have been donating its effective priority to $t_i$, so we need to recalculate $p_{ei}$.
\item When a thread $t_i$ acquires a queue $q$, we need to make sure that $p_ei$ is set to the largest effective priority of any thread $t_j$ in that queue. However, $t_i$ can only acquires $q$ if its effective priority is at least as large as any other thread $t_j \in q$. So we do not need to change the effective priority of a thread upon acquisition of a new queue.
\item Note that a thread $t_i$ gives up ownership of a queue $q$, either when {\tt nextThread} is called on $q$ while $t_i$ owns it, or when waitForAccess is called on $q$ and $t_i$, moving $t_i$ to the back of the line. When either of these events happen, we may need to lower $p_{ei}$, since $t_i$ is no longer owning a queue that might have been giving $t_i$ its effective priority. So at this point we need to recalculate $p_{ei}$, taking into account only queues that $t_i$ owns after relinquishing $q$.

\end{itemize}

We cache the effective priority of each thread. We recalculate it as follows. Any time the queue changes so that a different thread is placed at the head of the queue, we cheack to see if that thread's effective priority is higher than that of the thread that owns the queue (if any). If it is, we ``donate'' the priority of the thread at the head of the queue to the thread that owns the queue. This takes $O(1)$ time.

Any time a thread loses ownership of a queue we recalculate its effective priority by looking at the (cached) effective priorities of all threads that are at the head of any queues that the thread still owns. This takes $O(m)$ time, where $m$ is the number of queues.

\subsubsection{PriorityQueue Operations}

These are some of the more important private and public operations on {\tt PriorityQueue}.

\paragraph{left, right, and parent}

These operations take an index of a thread in the heap and return the index of its left child, right child, and parent, respectively. The ordering is described by Cormen, Leiserson, Rivest, and Stein.

\paragraph{heapify}

This is taken straight from Cormen, Leiserson, Rivest, and Stein. It is called on a thread in the heap, and restores the heap property by moving the thread down in the heap until it is no longer larger than its parent. 

\paragraph{bubbleUp}

This is an important operation of the PriorityQueue class that is called on a ThreadState $t$. It assumes that $t$ might be lower in the heap than it should be. It moves $t$ up to the proper place in the heap by repeatedly swapping it with its parent until it is no larger than its parent. If this causes $t$ to rise all the way to the top of the heap, and $t$'s effective priority is higher than the current owner of the queue, we donate the $t$'s effective priority to the owner, and then recursively call {\tt bubbleUp} on the owner. After bubbleUp returns, all threads should be in their proper places in their wait queus, and all priority donations should be complete.

\paragraph{waitForAccess}

When waitForAccess is called on a thread, we check to see if it currently owns that queue. If it does, we break that ownership. We add the thread to the end of the heap, and then move it up to its proper position in the heap and perform any necessary priority donations by calling {\tt bubbleUp}.

\paragraph{nextThread}

When {\tt nextThread} is called on a queue, we first check if another thread owns the queue, and if so, break the ownership. This may cause that thread's effective priority to be lowered because it may no longer be blocking higher-priority threads, so we recalculate its effective priority. We then pop the top thread off of the heap, set it as the queues owner, update its {\tt ownedQueues} property to indicate that it owns the queue, and return it. After we pop the top thread, we need to call heapify to restore the max-heap property.

\paragraph{setPriority}

When {\tt setPriority} is called on a {\tt ThreadState}, we check whether the new priority is higher or lower than the thread's old priority. If it is higher, then we just call {\tt bubbleUp} to move the thread up to its proper place in the heap and handle any priority donations that need to take place. If it is lower, we have a little more work to do since max-heaps don't directly support a decrease-key operation. We first artificually raise the effective priority of the thread so that it is higher than any other thread, bubble it up to the top of the heap, and pop it off. Then we restore the thread's priority to what it should be set to, and then add it back on the heap.

\subsection{Boat Simulation}

The boat simulation is completely build in the Boat.java file. 
No new functions have been added to this class. 
Numerous variables have been added to handle the sync-ing of the threads and determining the completion.
\begin{itemize}
\item boatlock - master lock for accessing the boat and associated variables. 
\item cbl\_oahu - condition variable for threads waiting on Oahu
\item cbl\_molokai - condition variable for threads waiting on Molokai
\item cbl\_passenger - condition variable to be used on Oahu when a pilot has boarded and the pilot is a child and there are other children on Oahu
\item talker - Communcator to tell begin, a thread thinks it is done
\item ending - integer signal for talking to the begin thread
\item locOahu, locMolokai - integers to differentiate locations
\item noPilot, pChild, pAdult - integers to differentiate the current pilot
\item boatPilot - variable to store the current pilot
\item boatPassenger - a flag to indicate that a passenger has boarded
\item boatLocation - the current location of the boat
\item childrenOnMolokai - the number of children on Molokai (\textit{only to be used on Molokai})
\item adultsOnMolokai - the number of adults on Molokai (\textit{only to be used on Molokai})
\item childrenOnOahu - the number of children on Oahu (\textit{only to be used on Oahu})
\item adultsOnOahu - the number of adults on Oahu (\textit{only to be used on Oahu})
\item allPeopleOnMolokai - a boolean to signal the end of processing
\end{itemize}

Currently with allPeopleOnMolokai signal, the threads are not stopping when either waiting or processing because it appears the machine is halting before this occurs. 
This was not further checked into because the assignment didn't require the adult and children threads to terminate - only the entire simulation.

The begin thread setups the global static variables for the individual threads and then spawns each thread off. 
begin also prevents any early thread from starting until it finishes creating all of the individual threads. 
After spawning the threads and releasing the boatlock, the begin threads waits for one of the individual threads to say they think it has ended and then checks and if so will end the simulation.

The adultItinerary function is the thread processing for the adult threads. 
The function simply increments the adultsOnOahu variable at the start and then will attempt to acquire the boat from Oahu. 
If acquired, it will send the boat to Molokai and release the boatlock.
As part of this it also checks if the adult was the last one on Oahu and will signal the begin thread accordingly. 
If the boat is acquired on Molokai, the adult can also transfer back to Oahu.
There is a check, however, to prevent an adult from locking the boat if the adult thinks there are children on the island (children also have higher priority on Molokai).

The childItinerary function is similar in processing to the adult version.
The main difference is that on Oahu if the child thinks there are other children on Oahu, it will hold up the boat until a child boards as a passenger. 
Both the pilot and passenger check if they are the last one off the island to inform begin of completion. 
When returning from Molokai to Oahu, the child threads prevent a second child from being on the boat. 

The overall algorithm is to send two children from Oahu to Molokai as much as possible and then transfer the adults over one by one. 
For this to work, a child must be on Molokai in advance so the adult doesn't have to immediately return to Oahu (1 adult per boat trip): hence the 2 children to Molokai and only one can return to Oahu.
On Molokai, an adult does not attempt to leave unless they think there are no children on Molokai. 
On Oahu, it is basically a ``free-for-all'' for accessing the boat and the first to get it will be traveling to Molokai. 
The other logic will help out getting the entire algorithm to work. 

Obviously discussion of using Priority scheduling has been avoided at this point. 
These algorithms where tested in both RoundRobin and Priority scheduling and worked in both. 
A quick visual seemed to indicate that Priority worked a little better (a few deadlocks where actually found using RoundRobin). 
In any case, the PrioritySchedule properly simulates the people going from Oahu to Molokai. 
As part of this, there were changes to thread priorities during the processing. 
An adult's priority dropped when arriving on Molokai and was raised upon return on Oahu. 
A child's priority raised when arriving on Molokai and lowered upon return to Oahu.
The priority changing helps the situation in general but the problem is solvable without it (just not as quickly).


\section{Running}

The modified files in thread package are:
\begin{itemize}
\item Alarm.java
\item Boat.java
\item Communicator.java
\item Condition2.java
\item KThread.java
\item PriorityScheduler.java
\item ThreadedKernel.java (only self test code)
\end{itemize}


To run the program, it is simple to have the files in the normal nachos distribution plus the ones above in the threads package.
First go to the proj1 directory, then simply type \textit{gmake} [enter], and then \textit{../bin/nachos} [enter]. 
The KThread.selfTest runs the tests and spawns off Boat.selfTest() which has a test method using 11 adults and 10 children.



\end{document}
